/**
 * ConvertNFA.java
 *
 * Created by Chad Cross on 4/5/09.
 * 
 * @author Chad Cross
 * @version 1.2
 *
 * This class converts an NFA to a DFA using subset construction.
 *
 * Adapted from Amer Gerzic's regex library: http://www.amergerzic.com/page/Free-Downloads.aspx
 * Licensed under the Code Project Open License: http://www.codeproject.com/info/cpol10.aspx
 *
 */

package jmai.parser;

import java.util.*;

public class ConvertNFA {
	
	/** A TreeMap for the NFA */
	@SuppressWarnings("unchecked")
	private TreeMap NFATreeMap = new TreeMap();
	
	/** A TreeMap for the DFA */
	@SuppressWarnings("unchecked")
	private TreeMap DFATreeMap = new TreeMap();
	
	/** An ArrayList for the input string */
	@SuppressWarnings("unchecked")
	public ArrayList inputArray = new ArrayList();
	
	/** The start state of the NFA */
	private String startStateNFAName;
	
	/** The start state of the DFA */
	private String startStateDFA;
	
	/**
	 * The default constructor for coding standards
	 */
	public ConvertNFA() {
	
	}//end constructor
	
	/**
	 * Converts an NFA to a DFA using subset construction
	 * @return Boolean true if the conversion was successful
	 */
	@SuppressWarnings("unchecked")
	public boolean ConvertToDFA() {
		
		ArrayList unprocessedNodes = new ArrayList();
		
		TreeSet processedTreeSet = new TreeSet();
		
		State startStateNFA = (State)NFATreeMap.get(startStateNFAName);
		
		if(startStateNFA == null) {
			return false;
		}//end if
		
		//Begin the construction using the start state of the DFA
		ArrayList setState = eClosure(startStateNFA);
		startStateNFA = new State(setState);
		
		startStateDFA = startStateNFA.stateName;
		
		//add the state to the DFA tree
		
		DFATreeMap.put(startStateDFA, startStateNFA);
		
		unprocessedNodes.add(startStateNFA);
		
		while(!unprocessedNodes.isEmpty()) {
			
			/** Get the DFA state to be processed */
			State DFAState = (State)unprocessedNodes.get(0);
			DFATreeMap.put(DFAState.stateName, DFAState);
			unprocessedNodes.remove(0);
		
		
			if (processedTreeSet.contains(DFAState))
				continue;
			
			processedTreeSet.add(DFAState);
			
			for (int i = 0; i < inputArray.size(); ++i) {
				TreeSet moveSet = new TreeSet();
				
				for (int j = 0; j < DFAState.NFAStates.size(); ++j) {
					
					ArrayList searchArray = Search((State)DFAState.NFAStates.get(j), (String)inputArray.get(i));
					if(searchArray != null) 
						moveSet.addAll(searchArray);
				}//end for
				
				//Apply the e-closures to our new state of states
				
				TreeSet eClosureSet = new TreeSet();
				Iterator iter = moveSet.iterator();
				
				
				while(iter.hasNext()) {
					State tempState = (State)iter.next();
					
					ArrayList closureArray = eClosure(tempState);
					
					eClosureSet.addAll(closureArray);
				}//end while
				
				//check to see if there any new states as a result of computing e-closures
				
				if (eClosureSet.size() > 0) {
					State newState = new State(new ArrayList(eClosureSet));
					if(!DFATreeMap.containsKey(newState.stateName)) {
						DFATreeMap.put(newState.stateName, newState);
					}//end if
					else {
						newState = (State)DFATreeMap.get(newState.stateName);

					}//end else
					
					unprocessedNodes.add(newState);
					
					//Create a transition to this new state
					
					Transition t = new Transition((String)inputArray.get(i));
					t.stateArray.add(newState);
					DFAState.transitionsArray.add(t);
					
				}//end if
				
			}//end for
		}//end while
		
		return true;
	}//end method ConvertToNFA
	
	/**
	 * This method is used for calculating epsilon closure for a particular state
	 * @param state a state for which to compute epsilon transitions
	 * @return ArrayList a set of states reachable from this state via epsilon transitions
	 */
	@SuppressWarnings("unchecked")
	private ArrayList eClosure(State state) {
		Stack unprocessedStates = new Stack();
		
		unprocessedStates.push(state);
		
		TreeSet processedStates = new TreeSet();
		
		TreeSet resultingStates = new TreeSet();
		
		resultingStates.add(state);
		
		while(!unprocessedStates.empty()) {
			State processingState = (State)unprocessedStates.pop();
			
			processedStates.add(processingState);

			for (int i = 0; i < processingState.transitionsArray.size(); ++i) {
				Transition t = (Transition)processingState.transitionsArray.get(i);
			
				if(t.transitionChar.compareToIgnoreCase("epsilon") == 0) {
					for(int j = 0; j < t.stateArray.size(); ++j) {
						State s = (State) t.stateArray.get(j);
						resultingStates.add(s);
					
						if (!processedStates.contains(s)) {
							unprocessedStates.push(s);
						}//end if
					}//end for
				}//end if
			}//end for
		}//end while
		
		ArrayList resultingArray = new ArrayList();
		resultingArray.addAll(resultingStates);
		return(resultingArray);
	}//end method eClosure
	
	/**
	 * This method returns all states that are reachable from
	 * an input state and an input character	
	 * @param state the start state of the search
	 * @param inputChar the input character
	 * @return ArrayList set of states which can be reached 
	 * from state on input inputChar
	 */
	@SuppressWarnings("unchecked")
	private ArrayList Search(State state, String inputChar) {
		ArrayList resultingStates = new ArrayList();
		
		inputChar.trim();
		
		if(inputChar.length() == 0) {
			return null;
		}//end if
		
		for (int i = 0; i < state.transitionsArray.size(); ++i) {
			Transition transition = (Transition)state.transitionsArray.get(i);
			
			if (transition.transitionChar.compareTo(inputChar) == 0) {
				resultingStates.addAll(transition.stateArray);
				
				return resultingStates;
			}//end if
		}//end for
		
		return null;
	}//end method Search
	
	//Setters
	
	/**
	 * Sets the name of the start state of the NFA
	 * @param startState The name of the start state
	 */
	public void setStartStateNFA(String startStateName) {
		startStateNFAName = startStateName;
	}//end method setStartStateNFA
	
	//Getters
	
	/**
	 * Returns the number of states in the NFA
	 * @return Size of the NFA TreeMap
	 */
	public int getNFAStates() {
		return NFATreeMap.size();
	}//end method getNFAStates
	
	/**
	 * Returns the name of the DFA start state
	 * @return startStateDFA The name of the start state
	 */
	public String getStartStateDFA() {
		return startStateDFA;
	}//end method getStartState
	
	/**
	 * Returns the state object of the state name passed in
	 * @param stateName The state to retrieve
	 * @return state The state object that is retrieved
	 */
	public State getStateNFA(String stateName) {
		State state = null;
		
		try {
			state = (State)NFATreeMap.get(stateName);
		}//end try block
		catch (ClassCastException cce) {
			return null;
		}//end catch block
		catch (NullPointerException npe) {
			return null;
		}//end catch block
		
		return state;
	}//end method getStateNFA
	
	/**
	 * Returns the TreeMap of the DFA
	 * @return the TreeMap representing the DFA
	 */
	@SuppressWarnings("unchecked")
	public TreeMap getDFATreeMap() {
		return DFATreeMap;
	}//end method getDFATreeMap
	
	//public void ResetTreeMaps() {
	//	NFATreeMap = new TreeMap();
	//	DFATreeMap = new TreeMap();
	//	inputArray = new ArrayList();
	//}
	
	@SuppressWarnings("unchecked")
	public boolean addNFAState(State s) {
		
		/** If the state is empty, there is nothing to do */
		if(s.stateName.length() == 0) {
			return false;
		}//end if
		
		/** If the state name already exists, there is nothing to do */
		if(NFATreeMap.containsKey(s.stateName)) {
			return false;
		}//end if
		
		/** 
		 * If the state is not null and it doesn't already exist,
		 * we can add it to the tree map
		 */
		try {
			NFATreeMap.put(s.stateName, s);
		}//end try block
		catch(ClassCastException cce) {
			return false;
		}//end catch block
		catch(NullPointerException e) {
			return false;
		}//end catch block
		
		return true;
	}//end method addNFAState
	
	/**
	 * This helper function will add a transition to an NFA given the name
	 * of an NFA state and the transition to be added
	 * @return True if state exists, False otherwise
	 */
	@SuppressWarnings("unchecked")
	public boolean addStateTransitionNFA(String stateName, Transition t) {
		State state = getStateNFA(stateName);
		
		if (state == null) {
			return false;
		}//end if
		else {
			state.transitionsArray.add(t);
			return true;
		}//end else
	}//end method addStateTransitionNFA
	
	/**
	 * This method adds an input character to the input ArrayList
	 * @param inputChar The character to add
	 * @return True if a character is added, false if nothing is added
	 */
	@SuppressWarnings("unchecked")
	public boolean addInputChar(String inputChar) {
		
		if(inputChar.compareToIgnoreCase("epsilon") == 0) {
			return true;
		}//end if
		
		if(inputChar.length() != 1) {
			return false;
		}//end if
		
		inputArray.add(inputChar);		
		return true;
	}//end method addInputChar
}//end class ConvertNFA
